home *** CD-ROM | disk | FTP | other *** search
/ PC World Interactive 7 / PC World Interactive 7.iso / program / ctutor.exe / TEXT / CHAP12.TXT < prev    next >
Text File  |  1994-05-15  |  25KB  |  522 lines

  1.  
  2.  
  3.  
  4.                                                        Chapter 12
  5.                                                DYNAMIC ALLOCATION
  6.  
  7. WHAT IS DYNAMIC ALLOCATION?
  8. -----------------------------------------------------------------
  9. Dynamic allocation is very intimidating to a      ===============
  10. person the first time he comes across it, but        DYNLIST.C
  11. that need not be.  Simply relax and read this     ===============
  12. chapter carefully and you will have a good 
  13. grounding in a very valuable programming resource.  All of the 
  14. variables in every program up to this point have been static 
  15. variables as far as we are concerned.  (Actually, some of them 
  16. have been automatic and were dynamically allocated for you by the 
  17. system, but it was transparent to you.)  In this chapter, we will 
  18. study some dynamically allocated variables.  They are variables 
  19. that do not exist when the program is loaded, but are created 
  20. dynamically as they are needed while the program is running.  
  21. It is possible, using these techniques, to create as many 
  22. variables as needed, use them, and deallocate their memory space 
  23. for reuse by other variables.  As usual, the best teacher is an 
  24. example, so examine the program named DYNLIST.C.
  25.  
  26. We begin by defining a named structure, animal, with a few fields 
  27. pertaining to dogs.  We do not define any variables of this type, 
  28. only three pointers.  If you search through the remainder of the 
  29. program, you will find no variables defined, so we have nothing 
  30. to store data in.  All we have to work with are three pointers, 
  31. each of which point to the defined structure.  In order to do 
  32. anything, we need some variables, so we will create some 
  33. dynamically.
  34.  
  35.  
  36. DYNAMIC VARIABLE CREATION
  37. -----------------------------------------------------------------
  38. The statement in line 14, which assigns something to the pointer 
  39. pet1 will create a dynamic structure containing three variables.  
  40. The heart of the statement is the malloc() function buried in the 
  41. middle of the statement.  This is a memory allocate function that 
  42. needs the other things to completely define it.  The malloc() 
  43. function, by default, will allocate a piece of memory on a heap 
  44. that is "n" characters in length and will be of type character.  
  45. The "n" must be specified as the only argument to the function.  
  46. We will discuss "n" shortly, but first we need to define a heap.
  47.  
  48.  
  49. WHAT IS A HEAP?
  50. -----------------------------------------------------------------
  51. Every compiler has a set of limitations on it as to how big the 
  52. executable file can be, how many variables can be used, how long 
  53. the source file can be, etc.  One limitation placed on users by 
  54. most MS-DOS C compilers is a limit of 64K for the executable code 
  55. if you happen to be in the small memory model.  This is because 
  56.  
  57.                                                         Page 12-1
  58.  
  59.                                   Chapter 12 - Dynamic Allocation
  60.  
  61. the IBM-PC uses a microprocessor with a 64K segment size, and it 
  62. requires special calls to use data outside of a single segment.  
  63. In order to keep the program small and efficient, these calls are 
  64. not used in some MS-DOS implementations of C, and the memory 
  65. space is limited but still adequate for most programs. 
  66.  
  67. A heap is an area outside of this 64K boundary which can be 
  68. accessed by the program to store data and variables.  The data 
  69. and variables are put on the heap by the system as calls to 
  70. malloc() are made.  The system keeps track of where the data is 
  71. stored.  Data and variables can be deallocated as desired, 
  72. leading to holes in the heap.  The system knows where the holes 
  73. are and will use them for additional data storage as more 
  74. malloc() calls are made.  The structure of the heap is therefore 
  75. a very dynamic entity, changing constantly.
  76.  
  77.  
  78. MORE ABOUT SEGMENTS
  79. -----------------------------------------------------------------
  80. Most C compilers give the user a choice of memory models to use.  
  81. The user has a choice of using a model with a 64K limitation for 
  82. either program or data leading to a small fast program or 
  83. selecting a 640K limitation and requiring longer address calls 
  84. leading to less efficient addressing.  Using the larger address 
  85. space requires inter segment addressing, resulting in the 
  86. slightly slower running time.  The time is probably insignificant 
  87. in most programs, but there are other considerations.
  88.  
  89. If a program uses no more than 64K bytes for the total of its 
  90. code and memory and if it doesn't use a stack, it can be made 
  91. into a .COM file.  Since a .COM file is already in a memory image 
  92. format, it can be loaded very quickly whereas a file in an .EXE 
  93. format must have its addresses relocated as it is loaded.  
  94. Therefore a tiny memory model can generate a program that loads 
  95. faster than one generated with a larger memory model.  Don't let 
  96. this worry you, it is a fine point that few programmers worry 
  97. about.
  98.  
  99. Using dynamic allocation, it is possible to store the data on the 
  100. heap and that may be enough to allow you to use the small memory 
  101. model.  Of course, you wouldn't store local variables such as 
  102. counters and indexes on the heap, only very large arrays or 
  103. structures.
  104.  
  105. Even more important than the need to stay within the small memory 
  106. model is the need to stay within the computer.  If you had a 
  107. program that used several large data storage areas, but not at 
  108. the same time, you could load one block storing it dynamically, 
  109. then get rid of it and reuse the space for the next large block 
  110. of data.  Dynamically storing each block of data in succession, 
  111. and using the same storage for each block may allow you to run 
  112. your entire program in the computer without breaking it up into 
  113. smaller programs. 
  114.  
  115.                                                         Page 12-2
  116.  
  117.                                   Chapter 12 - Dynamic Allocation
  118.  
  119. BACK TO THE MALLOC FUNCTION
  120. -----------------------------------------------------------------
  121. Hopefully the above description of the heap and the overall plan 
  122. for dynamic allocation helped you to understand what we are doing 
  123. with the malloc() function.  It simply asks the system for a 
  124. block of memory of the size specified, and returns the block with 
  125. the pointer pointing to the first element of the block.  The only 
  126. argument in the parentheses is the size of the block desired and 
  127. in our present case, we desire a block that will hold one of the 
  128. structures we defined at the beginning of the program.  The 
  129. sizeof operator is new, new to us at least.  It returns the size 
  130. in bytes of the argument within its parentheses.  It therefore, 
  131. returns the size of the structure named animal, in bytes, and 
  132. that number is sent to the system with the malloc() call.  At the 
  133. completion of that call, we have a block on the heap allocated to 
  134. us, with the pointer named pet1 pointing to the block of data.
  135.  
  136.  
  137. WHAT IS A CAST?
  138. -----------------------------------------------------------------
  139. We still have a funny looking construct at the beginning of the 
  140. malloc() function call, which is called a cast.  The malloc() 
  141. function returns a block with the pointer pointing to it being a 
  142. pointer to type void by default.  You really cannot use a pointer 
  143. to void, so it must be changed to some other type.  You can 
  144. define the pointer type with the construct given on the example 
  145. line.  In this case we want the pointer to point to a structure 
  146. of type animal, so we tell the compiler with this strange looking 
  147. construct.  Even if you omit the cast, most compilers will return 
  148. a pointer correctly, give you a warning, and go on to produce a 
  149. working program.  It is better programming practice to provide 
  150. the compiler with the cast to prevent getting the warning 
  151. message.
  152.  
  153. The data space of the computer is depicted graphically by figure 
  154. 12-1 following execution of line 14.  The graphical notation 
  155. defines the pointer as pointing to the structure.  As far as the 
  156. program is concerned, the pointer is actually pointing to all 
  157. three members taken as a group rather than to the first element.
  158.  
  159.  
  160. USING THE DYNAMICALLY ALLOCATED STRUCTURE
  161. -----------------------------------------------------------------
  162. If you remember our studies of structures and pointers, you will 
  163. recall that if we have a structure with a pointer pointing to it, 
  164. we can access any of the variables within the structure.  In 
  165. lines 15 through 17 of the program, we assign some silly data to 
  166. the structure for illustration.  It should come as no surprise to 
  167. you that these assignment statements look just like assignments 
  168. to statically defined variables.  Figure 12-2 illustrates the 
  169. state of the data space at this point in the program execution.
  170.  
  171.  
  172.  
  173.                                                         Page 12-3
  174.  
  175.                                   Chapter 12 - Dynamic Allocation
  176.  
  177. In line 19, we assign the value of pet1 to pet2 also via a 
  178. pointer assignment statement which we introduced in chapter 8.  
  179. This creates no new data, we simply have two pointers to the same 
  180. object.  Since pet2 is pointing to the structure we created 
  181. above, pet1 can be reused to get another dynamically allocated 
  182. structure which is just what we do next.  Keep in mind that pet2 
  183. could have just as easily been used for the new allocation.  The 
  184. new structure is filled with silly data for illustration in lines 
  185. 22 through 24.
  186.  
  187. Finally, we allocate another block on the heap using the pointer 
  188. pet3, and fill its block with illustrative data. Figure 12-3 
  189. illustrates the condition of the data space after execution of 
  190. line 29 of the program.
  191.  
  192. Printing the data out should pose no problem to you since there 
  193. is nothing new in the three print statements.
  194.  
  195. Even though it is not illustrated in this tutorial, you can 
  196. dynamically allocate and use simple variables such as a single 
  197. char type variable.  This should be discouraged however since it 
  198. is very inefficient.
  199.  
  200.  
  201. GETTING RID OF THE DYNAMICALLY ALLOCATED DATA
  202. -----------------------------------------------------------------
  203. Another new function is used to get rid of the data and free up 
  204. the space on the heap for reuse, the function free().  To use it, 
  205. you simply call it with the pointer to the dynamically allocated 
  206. block of data as the only argument, and the block is deallocated.
  207.  
  208. In order to illustrate another aspect of the dynamic allocation 
  209. and deallocation of data, an additional step is included in the 
  210. program on your monitor.  The pointer pet1 is assigned the value 
  211. of pet3 in line 42.  In doing this, the block that pet1 was 
  212. pointing to is effectively lost since there is no pointer that 
  213. is now pointing to that block.  It can therefore never again be 
  214. referred to, changed, or deallocated.  That memory, which is a 
  215. block on the heap, is wasted from this point on.  This is not 
  216. something that you would ever purposely do in a program.  It is 
  217. only done here for illustration.
  218.  
  219. The first free() function call removes the block of data that 
  220. pet1 and pet3 were pointing to, and the second free() call 
  221. removes the block of data that pet2 was pointing to.  We 
  222. therefore have lost access to all of our data generated earlier.  
  223. There is still one block of data that is on the heap but there 
  224. is no pointer to it since we lost the address to it.  Figure 
  225. 12-4 illustrates the data space as it now appears.  Trying to 
  226. free the data pointed to by pet1 would result in an error because 
  227. it has already been freed by the use of pet3.  There is no need 
  228. to worry, however.  When we return to DOS, the entire heap will 
  229. be disposed of with no regard to what we have put on it.  The 
  230.  
  231.                                                         Page 12-4
  232.  
  233.                                   Chapter 12 - Dynamic Allocation
  234.  
  235. point does need to made that, if you lose a pointer to a block 
  236. of the heap, it forever removes that block of data storage from 
  237. our use and we may need that storage later.
  238.  
  239. Compile and run the program to see if it does what you think it 
  240. should do based on this discussion.
  241.  
  242.  
  243. THAT WAS A LOT OF DISCUSSION
  244. -----------------------------------------------------------------
  245. It took six pages to get through the discussion of the last 
  246. program but it was time well spent.  It should be somewhat 
  247. exciting to you to know that there is nothing else to learn about 
  248. dynamic allocation, the last six pages covered it all.  Of 
  249. course, there is a lot to learn about the technique of using 
  250. dynamic allocation, and for that reason, there are two more 
  251. example programs to study.  But the fact remains, there is 
  252. nothing more to learn about the technique of dynamic allocation 
  253. than what was given so far in this chapter.
  254.  
  255.  
  256. AN ARRAY OF POINTERS
  257. -----------------------------------------------------------------
  258. Load and display the file BIGDYNL.C for another   ===============
  259. example of dynamic allocation.  This program is      BIGDYNL.C
  260. very similar to the last one since we use the     ===============
  261. same structure, but this time we define an 
  262. array of pointers to illustrate the means by which you could 
  263. build a large database using an array of pointers rather than a 
  264. single pointer to each element.  To keep it simple we define 12 
  265. elements in the array and another working pointer named point.
  266.  
  267. The *pet[12] is new to you so a few words would be in order.  
  268. What we have defined is an array of 12 pointers, the first being 
  269. pet[0], and the last pet[11].  Actually, since an array is itself 
  270. a pointer, the name pet by itself is a pointer to a pointer.  
  271. This is valid in C, and in fact you can go farther if needed but 
  272. you will get quickly confused.  I know of no limit as to how many 
  273. levels of pointing are possible, so the definition int ****pt; is 
  274. legal as a pointer to a pointer to a pointer to a pointer to an 
  275. integer type variable, if I counted right.  Such usage is 
  276. discouraged until you gain considerable experience.
  277.  
  278. Now that we have 12 pointers which can be used like any other 
  279. pointer, it is a simple matter to write a loop to allocate a data 
  280. block dynamically for each and to fill the respective fields with 
  281. any data desirable.  In this case, the fields are filled with 
  282. simple data for illustrative purposes, but we could be reading 
  283. from a database, from some test equipment, or from any other 
  284. source of data.
  285.  
  286. A few fields are randomly picked in lines 24 through 26 to 
  287. receive other data to illustrate that simple assignments can be 
  288.  
  289.                                                         Page 12-5
  290.  
  291.                                   Chapter 12 - Dynamic Allocation
  292.  
  293. used, and the data is printed out to the monitor.  The pointer 
  294. point is used in the printout loop only to serve as an 
  295. illustration, the data could have been easily printed using the 
  296. pet[n] means of definition.  Finally, all 12 blocks of data are 
  297. freed before terminating the program.
  298.  
  299. Compile and run this program to aid in understanding this 
  300. technique.  As stated earlier, there was nothing new here about 
  301. dynamic allocation, only about an array of pointers.
  302.  
  303.  
  304. A LINKED LIST
  305. -----------------------------------------------------------------
  306. We finally come to the granddaddy of all        =================
  307. programming techniques as far as being              DYNLINK.C
  308. intimidating.  Load the program DYNLINK.C       =================
  309. for an example of a dynamically allocated 
  310. linked list.  It sounds terrible, but after a little time spent 
  311. with it, you will see that it is simply another programming 
  312. technique made up of simple components that can be a powerful 
  313. tool.
  314.  
  315. In order to set your mind at ease, consider the linked list you 
  316. used when you were a child.  Your sister gave you your birthday 
  317. present, and when you opened it, you found a note that said, 
  318. "Look in the hall closet."  You went to the hall closet, and 
  319. found another note that said, "Look behind the TV set."  Behind 
  320. the TV you found another note that said, "Look under the coffee 
  321. pot."  You continued this search, and finally you found your pair 
  322. of socks under the dogs feeding dish.  What you actually did was 
  323. to execute a linked list, the starting point being the wrapped 
  324. present and the ending point being under the dogs feeding dish.  
  325. The list ended at the dogs feeding dish since there were no more 
  326. notes.
  327.  
  328. In the program DYNLINK.C, we will be doing the same thing your 
  329. sister forced you to do.  However, we will do it much faster and 
  330. we will leave a little pile of data at each of the intermediate 
  331. points along the way.  We will also have the capability to return 
  332. to the beginning and traverse the entire list again and again if 
  333. we so desire.
  334.  
  335.  
  336. THE DATA DEFINITIONS
  337. -----------------------------------------------------------------
  338. This program starts similarly to the last two with the addition 
  339. of the definition of a constant to be used later.  The structure 
  340. is nearly the same as that used in the last two programs except 
  341. for the addition of another field within the structure in line 
  342. 11, the pointer.  This pointer is a pointer to another structure 
  343. of this same type and will be used to point to the next structure 
  344. in order.  To continue the above analogy, this pointer will point 
  345.  
  346.  
  347.                                                         Page 12-6
  348.  
  349.                                   Chapter 12 - Dynamic Allocation
  350.  
  351. to the next note, which in turn will contain a pointer to the 
  352. next note after that.
  353.  
  354. We define three pointers to this structure for use in the 
  355. program, and one integer to be used as a counter, and we are 
  356. ready to begin using the defined structure for whatever purpose 
  357. we desire.  In this case, we will once again generate nonsense 
  358. data for illustrative purposes.
  359.  
  360.  
  361. THE FIRST FIELD
  362. -----------------------------------------------------------------
  363. Using the malloc() function, we request a block of storage on the 
  364. heap and fill it with data.  The additional field in this 
  365. example, the pointer, is assigned the value of NULL, which is 
  366. only used to indicate that this is the end of the list.  We will 
  367. leave the pointer named start pointing at this structure, so that 
  368. it will always point to the first structure of the list.  We also 
  369. assign prior the value of start for reasons we will see soon.  
  370. Keep in mind that the end points of a linked list will always 
  371. have to be handled differently than those in the middle of a 
  372. list.  We have a single element of our list now and it is filled 
  373. with representative data.  Figure 12-5 is the graphical 
  374. representation of the data space following execution of line 24.
  375.  
  376.  
  377. FILLING ADDITIONAL STRUCTURES
  378. -----------------------------------------------------------------
  379. The next group of assignments and control statements are included 
  380. within a for loop so we can build our list fast once it is 
  381. defined.  We will go through the loop a number of times equal to 
  382. the constant RECORDS defined at the beginning of our program.  
  383. Each time we go through the loop, we allocate memory, fill the 
  384. first three fields with nonsense, and fill the pointers.  The 
  385. pointer in the last record is given the address of this new 
  386. record because the prior pointer is pointing to the prior record.  
  387. Thus prior->next is given the address of the new record we have 
  388. just filled.  The pointer in the new record is assigned the value 
  389. NULL, and the pointer prior is given the address of this new 
  390. record because the next time we create a record, this one will be 
  391. the prior one at that time.  That may sound confusing but it 
  392. really does make sense if you spend some time studying it.
  393.  
  394. Figure 12-6 illustrates the data space following execution of the 
  395. loop two times.  The list is growing downward by one element each 
  396. time we execute the statements in the loop.  When we have gone 
  397. through the for loop 6 times, we will have a list of 7 structures 
  398. including the one we generated prior to the loop.  The list will 
  399. have the following characteristics.
  400.  
  401. 1.  The pointer named start points to the first structure in the 
  402.     list.
  403.     
  404.  
  405.                                                         Page 12-7
  406.  
  407.                                   Chapter 12 - Dynamic Allocation
  408.  
  409. 2.  Each structure contains a pointer to the next structure.
  410.  
  411. 3.  The last structure has a pointer containing the value NULL 
  412.     which can be used to detect the end.
  413.     
  414. It should be clear to you, if you understand the overall data 
  415. structure, that it is not possible to simply jump into the middle 
  416. of the list and change a few values.  The only way to get to the 
  417. third structure is by starting at the beginning and working your 
  418. way down through the list one record at a time.  Although this 
  419. may seem like a large price to pay for the convenience of putting 
  420. so much data outside of the program area, it is actually a very 
  421. good way to store some kinds of data.
  422.  
  423. A word processor would be a good application for this type of 
  424. data structure because you would never need to have random access 
  425. to the data.  In actual practice, this is the basic type of 
  426. storage used for the text in a word processor with one line of 
  427. text per record.  Actually, a program with any degree of 
  428. sophistication would use a doubly linked list.  This would be a 
  429. list with two pointers per record, one pointing down to the next 
  430. record, and the other pointing up to the record just prior to the 
  431. one in question.  Using this kind of a record structure would 
  432. allow traversing the data in either direction.
  433.  
  434.  
  435. PRINTING THE DATA OUT
  436. -----------------------------------------------------------------
  437. To print the data out, a similar method is used as that used to 
  438. generate the data.  The pointers are initialized and are then 
  439. used to go from record to record, reading and displaying each 
  440. record one at a time.  Printing is terminated when the NULL in 
  441. the last record is found, so the program doesn't even need to 
  442. know how many records are in the list.  Finally, the entire list 
  443. is deleted to make room in memory for any additional data that 
  444. may be needed, in this case, none.  Care must be taken to assure 
  445. that the last record is not deleted before the NULL is checked.  
  446. Once the data is gone, it is impossible to know if you are 
  447. finished yet.
  448.  
  449.  
  450. MORE ABOUT DYNAMIC ALLOCATION AND LINKED LISTS
  451. -----------------------------------------------------------------
  452. It is not difficult, nor is it trivial, to add elements into the 
  453. middle of a linked list.  It is necessary to create the new 
  454. record, fill it with data, and point its pointer to the record it 
  455. is desired to precede.  If the new record is to be installed 
  456. between the 3rd and 4th, for example, it is necessary for the new 
  457. record to point to the 4th record, and the pointer in the 3rd 
  458. record must point to the new one.  Adding a new record to the 
  459. beginning or end of a list are each special cases.  Consider what 
  460. must be done to add a new record in a doubly linked list. 
  461.  
  462.  
  463.                                                         Page 12-8
  464.  
  465.                                   Chapter 12 - Dynamic Allocation
  466.  
  467. Entire books are written describing different types of linked 
  468. lists and how to use them, so no further detail will be given.  
  469. The amount of detail given should be sufficient for a beginning 
  470. understanding of C and its capabilities.
  471.  
  472.  
  473. TWO MORE FUNCTIONS
  474. -----------------------------------------------------------------
  475. Two additional functions must be mentioned, the calloc() and the 
  476. realloc() functions.  The calloc() function allocates a block of 
  477. memory and clears it to all zeros which may be useful in some 
  478. circumstances.  It is similar to malloc() and will be left as an 
  479. exercise for you to read about and use calloc() if you desire.  
  480. Generally, you allocate a block of memory and immediately fill it 
  481. with meaningful data so it wastes time to fill it with zeros in 
  482. the calloc(), then fill it with real data.  For this reason, the 
  483. calloc() function is rarely used.
  484.  
  485. The realloc() is used to change the size of an allocated block, 
  486. either bigger or smaller.  You should ignore this until you gain 
  487. a lot of experience with C.  It is rarely used, even by 
  488. experienced programmers.
  489.  
  490.  
  491. PROGRAMMING EXERCISES
  492. -----------------------------------------------------------------
  493. 1.  Rewrite the example program STRUCT1.C from chapter 11 to 
  494.     dynamically allocate the two structures.
  495.     
  496. 2.  Rewrite the example program STRUCT2.C from chapter 11 to 
  497.     dynamically allocate the 12 structures.
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506.  
  507.  
  508.  
  509.  
  510.  
  511.  
  512.  
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.                                                         Page 12-9
  522.